//思路：先利用数组输入二叉树字符串，然后构建这个二叉树（构建的时候先是分开的点，等returns时候才会
//把二叉树串起来）
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct TreeNode{
	char val;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;
TreeNode* Rebuild(char* arr, int* pi)
{//节点构建思路：如果为#就return，如果不为空就构建左，然后构建右
	if (arr[(*pi)] == '#')
		return NULL;

	//每个节点都要自己malloc
	else
	{
		TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
		root->val = arr[*pi];
		(*pi)++;
		root->left = Rebuild(arr, pi);//这里就在完成牵引
		(*pi)++;
		root->right = Rebuild(arr, pi);
		return root;//最后返回的肯定是最上层的rot,就是二叉树的头节点
	}
}
void inorder(TreeNode* root)
{
	if (root == NULL)
		return;

	inorder(root->left);
	printf("%c ", root->val);
	inorder(root->right);
}
int main()
{

	char arr[100];
	//char* arr = (char*)malloc(sizeof(char));
	scanf("%s", arr);//这里不同于整形，arr已经是地址了不用取地址
	//构建二叉树
	int i = 0;//在构建二叉树的时候要用i遍历数组
	TreeNode* root = Rebuild(arr, &i);

	//中序遍历
	inorder(root);

	return 0;
}